Por que o processamento de uma matriz classificada é mais rápido do que o processamento de uma matriz não classificada?

Você é uma vítima da falha de previsão do ramo.
O que é a previsão de ramos?
Considere um entroncamento ferroviário:
Imagem de Mecanismo, via Wikimedia Commons. Usado sob a licença CC-By-SA 3.0.
Agora, para fins de argumentação, suponha que isso tenha acontecido nos anos 1800 - antes da longa distância ou da comunicação por rádio.
Você é o operador de um cruzamento e ouve um trem chegando. Você não tem idéia de para onde deve ir. Você para o trem para perguntar ao maquinista que direção ele deseja. E então você ajusta a chave apropriadamente.
Os trens são pesados ​​e têm muita inércia. Portanto, eles demoram uma eternidade para iniciar e desacelerar.
Existe uma maneira melhor? Você adivinha a direção em que o trem irá!
Se você adivinhou certo, ele continua.
Se você adivinhou errado, o capitão irá parar, recuar e gritar com você para girar a chave. Em seguida, ele pode reiniciar por outro caminho.
Se você acertar todas as vezes, o trem nunca terá que parar. Se você errar com muita frequência, o trem passará muito tempo parando, dando ré e reiniciando.
Considere uma instrução if: no nível do processador, é uma instrução de desvio:
Você é um processador e vê uma filial. Você não tem ideia de como isso vai acontecer. O que você faz? Você interrompe a execução e espera até que as instruções anteriores sejam concluídas. Então você continua no caminho correto.
Os processadores modernos são complicados e possuem longos canais. Por isso, demoram uma eternidade para "aquecer" e "abrandar".
Existe uma maneira melhor? Você adivinha em que direção o ramo irá!
Se você adivinhou certo, você continua executando.
Se você adivinhou errado, você precisa limpar o pipeline e voltar para o ramo. Em seguida, você pode reiniciar pelo outro caminho.
Se você acertar todas as vezes, a execução nunca terá que parar. Se você errar com muita frequência, perderá muito tempo travando, revertendo e reiniciando.
Esta é a previsão do ramo. Admito que não é a melhor analogia, já que o trem poderia apenas sinalizar a direção com uma bandeira. Mas em computadores, o processador não sabe para que direção uma ramificação irá até o último momento.
Então, como você imaginaria estrategicamente para minimizar o número de vezes que o trem deve voltar e descer pelo outro caminho? Você olha para a história passada! Se o trem sai 99% do tempo, então você acha que saiu. Se alternar, você alterna suas suposições. Se for em uma direção a cada três vezes, você adivinha o mesmo ...
Em outras palavras, você tenta identificar um padrão e segui-lo. É mais ou menos assim que funcionam os preditores de ramificação.
A maioria dos aplicativos tem ramificações bem comportadas. Portanto, os preditores de ramificação modernos normalmente atingirão taxas de acerto> 90%. Mas, quando confrontado com branches imprevisíveis sem padrões reconhecíveis, os preditores de branch são virtualmente inúteis.
Leitura adicional: artigo "Preditor de ramos" na Wikipedia.
Como sugerido acima, o culpado é esta declaração if:
if (dados [c]> = 128)
soma + = dados [c];
Observe que os dados são distribuídos uniformemente entre 0 e 255. Quando os dados são classificados, aproximadamente a primeira metade das iterações não entrará na instrução if. Depois disso, todos eles entrarão na instrução if.
Isso é muito amigável para o preditor de ramificação, uma vez que a ramificação segue consecutivamente na mesma direção muitas vezes. Mesmo um contador de saturação simples irá prever corretamente o ramo, exceto para as poucas iterações após a mudança de direção.
Visualização rápida:
T = ramo tomado
N = ramo não tomado
dados [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
ramo = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (fácil de prever)
No entanto, quando os dados são completamente aleatórios, o preditor de ramificação se torna inútil, porque ele não pode prever dados aleatórios. Portanto, provavelmente haverá cerca de 50% de predição incorreta (não melhor do que adivinhação aleatória).
dados [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
ramo = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completamente aleatório - difícil de prever)
Então, o que pode ser feito?
Se o compilador não for capaz de otimizar o branch para uma movimentação condicional, você pode tentar alguns hacks se estiver disposto a sacrificar a legibilidade pelo desempenho.
Substituir:
if (dados [c]> = 128)
soma + = dados [c];
com:
int t = (dados [c] - 128) >> 31;
soma + = ~ t & dados [c];
Isso elimina a ramificação e a substitui por algumas operações bit a bit.
(Observe que este hack não é estritamente equivalente à instrução if original. Mas, neste caso, é válido para todos os valores de entrada de data [].)
Benchmarks: Core i7 920 @ 3,5 GHz
C ++ - Visual Studio 2010 - Versão x64
// Branch - Random
segundos = 11,777
// Branch - Sorted
segundos = 2,352
// Branchless - Random
segundos = 2,564
// Branchless - Sorted
segundos = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Branch - Random
segundos = 10,93293813
// Branch - Sorted
segundos = 5,643797077
// Branchless -Aleatória
segundos = 3,113581453
// Branchless - Sorted
segundos = 3,186068823
Observações:
Com o Branch: Há uma grande diferença entre os dados classificados e não classificados.
Com o hack: não há diferença entre dados classificados e não classificados.
No caso do C ++, o hack é realmente um pouco mais lento do que com o branch quando os dados são classificados.
Uma regra geral é evitar ramificações dependentes de dados em loops críticos (como neste exemplo).
Atualizar:
O GCC 4.6.1 com -O3 ou -ftree-vectorize em x64 é capaz de gerar um movimento condicional. Portanto, não há diferença entre os dados classificados e não classificados - ambos são rápidos.
(Ou um pouco rápido: para o caso já classificado, cmov pode ser mais lento, especialmente se o GCC colocá-lo no caminho crítico em vez de apenas adicionar, especialmente em Intel antes de Broadwell, onde cmov tem latência de 2 ciclos: sinalizador de otimização gcc -O3 torna o código mais lento do que -O2)
O VC ++ 2010 não é capaz de gerar movimentos condicionais para este branch, mesmo em / Ox.
Intel C ++ Compiler (ICC) 11 faz algo milagroso. Ele troca os dois loops, içando assim o ramo imprevisível para o loop externo. Portanto, não só é imune a previsões erradas, como também é duas vezes mais rápido do que qualquer coisa que o VC ++ e o GCC possam gerar! Em outras palavras, o ICC aproveitou o loop de teste para derrotar o benchmark ...
Se você der ao compilador Intel o código sem ramificação, ele simplesmente o vetorizará ... e será tão rápido quanto com o branch (com o intercâmbio de loop).
Isso mostra que mesmo compiladores modernos maduros podem variar muito em sua capacidade de otimizar o código ...
|
Previsão de ramo.
Com uma matriz classificada, os dados de condição [c]> = 128 são primeiro falsos para uma sequência de valores e, em seguida, tornam-se verdadeiros para todos os valores posteriores. Isso é fácil de prever. Com uma matriz não classificada, você paga pelo custo de ramificação.
|
A razão pela qual o desempenho melhora drasticamente quando os dados são classificados é que a penalidade de previsão de branch é removida, conforme explicado lindamente na resposta de Mysticial.
Agora, se olharmos para o código
if (dados [c]> = 128)
soma + = dados [c];
podemos descobrir que o significado dessa ramificação if ... else ... particular é adicionar algo quando uma condição for satisfeita. Esse tipo de ramificação pode ser facilmente transformado em uma instrução de movimentação condicional, que seria compilada em uma instrução de movimentação condicional: cmovl, em um sistema x86. O ramo e, portanto, a penalidade de previsão de ramo potencial são removidos.
Em C, portanto C ++, a instrução, que seria compilada diretamente (sem qualquer otimização) na instrução de movimento condicional em x86, é o operador ternário ...? ...: .... Portanto, reescrevemos a declaração acima em uma equivalente:
soma + = dados [c]> = 128? dados [c]: 0;
Enquanto mantemos a legibilidade, podemos verificar o fator de aceleração.
Em um Intel Core i7-2600K @ 3.4 GHz e Visual Studio 2010 Release Mode, o benchmark é (formato copiado de Mysticial):
x86
// Branch - Random
segundos = 8,885
// Branch - Sorted
segundos = 1,528
// Branchless - Random
segundos = 3,716
// Branchless - Sorted
segundos = 3,71
x64
// Branch - Random
segundos = 11,302
// Branch - Sorted
segundos = 1.830
// Branchless - Random
segundos = 2,736
// Branchless - Sorted
segundos = 2,737
O resultado é robusto em vários testes. Conseguimos uma grande aceleração quando o resultado do branch é imprevisível, mas sofremos um pouco quando é previsível. Na verdade, ao usar um movimento condicional, o desempenho é o mesmo, independentemente do padrão de dados.
Agora vamos examinar mais de perto, investigando o assembly x86 que eles geram. Para simplificar, usamos duas funções max1 e max2.
max1 usa o desvio condicional if ... else ...:
int max1 (int a, int b) {
if (a> b)
return a;
outro
return b;
}
max2 usa o operador ternário ...? ...: ...:
int max2 (int a, int b) {
retornar a> b? a: b;
}
Em uma máquina x86-64, GCC -S gera o assembly abaixo.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
sair
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
sair
ret
max2 usa muito menos código devido ao uso da instrução cmovge. Mas o ganho real é que max2 não envolve saltos de ramificação, jmp, o que teria uma penalidade de desempenho significativa se o resultado previsto não fosse correto.
Então, por que um movimento condicional tem um desempenho melhor?
Em um processador x86 típico, a execução de uma instrução é dividida em vários estágios. Em termos gerais, temos hardware diferente para lidar com diferentes estágios. Portanto, não precisamos esperar que uma instrução termine para iniciar uma nova. Isso é chamado de pipelining.
Em um caso de ramificação, a instrução a seguir é determinada pela anterior, portanto, não podemos fazer pipelining. Temos que esperar ou prever.
Em um caso de movimentação condicional,a instrução de movimento condicional de execução é dividida em vários estágios, mas os estágios anteriores como Buscar e Decodificar não dependem do resultado da instrução anterior; apenas os estágios posteriores precisam do resultado. Assim, esperamos uma fração do tempo de execução de uma instrução. É por isso que a versão de movimentação condicional é mais lenta do que a ramificação quando a previsão é fácil.
O livro Computer Systems: A Programmer's Perspective, segunda edição explica isso em detalhes. Você pode verificar a Seção 3.6.6 para obter instruções de movimentação condicional, todo o capítulo 4 para a arquitetura do processador e a seção 5.11.2 para obter informações sobre o tratamento especial para previsão de ramificação e penalidades por erro de previsão.
Às vezes, alguns compiladores modernos podem otimizar nosso código para montagem com melhor desempenho, às vezes alguns compiladores não podem (o código em questão está usando o compilador nativo do Visual Studio). Saber a diferença de desempenho entre uma ramificação e uma movimentação condicional quando imprevisível pode nos ajudar a escrever código com melhor desempenho quando o cenário se torna tão complexo que o compilador não consegue otimizá-lo automaticamente.
|
Se você estiver curioso sobre ainda mais otimizações que podem ser feitas neste código, considere o seguinte:
Começando com o loop original:
para (sem sinal i = 0; i <100000; ++ i)
{
para (não assinado j = 0; j  = 128)
soma + = dados [j];
}
}
Com o intercâmbio de loop, podemos alterar esse loop com segurança para:
para (não assinado j = 0; j  = 128)
soma + = dados [j];
}
}
Então, você pode ver que o if condicional é constante em toda a execução do loop i, então você pode içar o if:
para (não assinado j = 0; j  = 128)
{
para (sem sinal i = 0; i <100000; ++ i)
{
soma + = dados [j];
}
}
}
Então, você vê que o loop interno pode ser reduzido em uma única expressão, assumindo que o modelo de ponto flutuante permite (/ fp: rápido é lançado, por exemplo)
para (não assinado j = 0; j  = 128)
{
soma + = dados [j] * 100000;
}
}
Esse é 100.000 vezes mais rápido do que antes.
|
Sem dúvida, alguns de nós estariam interessados ​​em maneiras de identificar o código que é problemático para o preditor de ramificação da CPU. A ferramenta Valgrind cachegrind possui um simulador de preditor de ramificação, habilitado usando o sinalizador --branch-sim = yes. Executando-o sobre os exemplos nesta pergunta, com o número de loops externos reduzido para 10.000 e compilado com g ++, obtém-se estes resultados:
Ordenado:
== 32551 == Filiais: 656.645.130 (656.609.208 cond + 35.922 ind)
== 32551 == Erros de previsão: 169.556 (169.095 cond + 461 ind)
== 32551 == Taxa de mispred: 0,0% (0,0% + 1,2%)
Não triados:
== 32555 == Ramos: 655.996.082 (655.960.160 cond + 35.922 ind)
== 32555 == Erros de previsão: 164.073.152 (164.072.692 cond + 460 ind)
== 32555 == Taxa de mispred: 25,0% (25,0% + 1,2%)
Analisando a saída linha por linha produzida por cg_annotate, vemos o loop em questão:
Ordenado:
Bc Bcm Bi Bim
10.001 4 0 0 para (sem sinal i = 0; i <10000; ++ i)
. . . . {
. . . . // loop primário
327.690.000 10.016 0 0 para (sem sinal c = 0; c  = 128)
0 0 0 0 soma + = dados [c];
. . . . }
. . . . }
Não triados:
Bc Bcm Bi Bim
10.001 4 0 0 para (sem sinal i = 0; i <10000; ++ i)
. . . . {
. . . . // loop primário
327.690.000 10.038 0 0 para (não assinado c = 0; c  = 128)
0 0 0 0 soma + = dados [c];
. . . . }
. . . . }
Isso permite que você identifique facilmente a linha problemática - na versão não classificada, a linha if (dados [c]> = 128) está causando 164.050.007 ramificações condicionais incorretas (Bcm) no modelo preditor de ramificação do cachegrind, enquanto está causando apenas 10.006 na versão classificada .
Como alternativa, no Linux, você pode usar o subsistema de contadores de desempenho para realizar a mesma tarefa, mas com desempenho nativo usando contadores de CPU.
perf stat ./sumtest_sorted
Ordenado:
Estatísticas do contador de desempenho para './sumtest_sorted':
11808.095776 task-clock # 0.998 CPUs utilizadas
1.062 chaves de contexto # 0,090 K / s
14 migrações de CPU # 0,001 K / s
337 falhas de página # 0,029 K / s
26.487.882.764 ciclos # 2.243 GHz
41.025.654.322 instruções # 1.55 insns por ciclo
6.558.871.379 ramos # 555.455 M / s
567.204 branch-misses # 0,01% de todos os branches
11,827228330 segundos de tempo decorrido
Não triados:
atuaçãoestatísticas de contador para './sumtest_unsorted':
28877.954344 CPU do clock de tarefa # 0.998 utilizada
2.584 chaves de contexto # 0,089 K / s
18 migrações de CPU # 0,001 K / s
335 falhas de página # 0,012 K / s
65.076.127.595 ciclos # 2.253 GHz
41.032.528.741 instruções # 0,63 insns por ciclo
6.560.579.013 ramos # 227.183 M / s
1.646.394.749 ramos perdidos # 25.10% de todos os ramos
28,935500947 segundos tempo decorrido
Ele também pode fazer anotações de código-fonte com desmontagem.
registro de perf -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Por cento | Código-fonte e desmontagem de sumtest_unsorted
------------------------------------------------
...
: soma + = dados [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39,97: 400a1d: mov% eax,% eax
5,31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: cltq
0,00: 400a28: adicionar% rax, -0x30 (% rbp)
...
Consulte o tutorial de desempenho para obter mais detalhes.
|
Acabei de ler sobre esta pergunta e suas respostas, e sinto que uma resposta está faltando.
Uma maneira comum de eliminar a previsão de branch que eu descobri que funciona particularmente bem em linguagens gerenciadas é uma pesquisa de tabela em vez de usar um branch (embora eu não tenha testado neste caso).
Essa abordagem funciona em geral se:
é uma pequena mesa e provavelmente será armazenada em cache no processador, e
você está executando as coisas em um loop bastante restrito e / ou o processador pode pré-carregar os dados.
Contexto e por quê
Do ponto de vista do processador, sua memória é lenta. Para compensar a diferença de velocidade, alguns caches são integrados ao processador (cache L1 / L2). Então imagine que você está fazendo seus cálculos bonitos e descubra que você precisa de um pedaço de memória. O processador obterá sua operação de 'carregamento' e carregará a parte da memória no cache - e então usará o cache para fazer o resto dos cálculos. Como a memória é relativamente lenta, esse 'carregamento' tornará seu programa mais lento.
Como a previsão de ramificação, isso foi otimizado nos processadores Pentium: o processador prevê que precisa carregar um pedaço de dados e tenta carregá-los no cache antes que a operação realmente atinja o cache. Como já vimos, a previsão de branch às vezes dá terrivelmente errado - no pior cenário, você precisa voltar e realmente esperar por um carregamento de memória, que levará uma eternidade (em outras palavras: a previsão de branch falhando é ruim, uma memória carregar após uma falha de previsão de branch é simplesmente horrível!).
Felizmente para nós, se o padrão de acesso à memória for previsível, o processador irá carregá-lo em seu cache rápido e tudo ficará bem.
A primeira coisa que precisamos saber é o que é pequeno? Embora menor seja geralmente melhor, uma regra prática é manter tabelas de pesquisa com tamanho <= 4096 bytes. Como um limite superior: se sua tabela de pesquisa for maior que 64K, provavelmente vale a pena reconsiderar.
Construindo uma mesa
Então, descobrimos que podemos criar uma pequena mesa. A próxima coisa a fazer é implementar uma função de pesquisa. As funções de pesquisa são geralmente pequenas funções que usam algumas operações inteiras básicas (e, ou, xor, deslocar, adicionar, remover e talvez multiplicar). Você deseja que sua entrada seja traduzida pela função de pesquisa em algum tipo de 'chave exclusiva' em sua tabela, que então simplesmente fornece a resposta de todo o trabalho que você deseja que ela faça.
Neste caso:> = 128 significa que podemos manter o valor, <128 significa que nos livramos dele. A maneira mais fácil de fazer isso é usando um 'AND': se o mantivermos, faremos AND com 7FFFFFFF; se quisermos nos livrar dele, fazemos AND com 0. Observe também que 128 é uma potência de 2 - então podemos ir em frente e fazer uma tabela de 32768/128 inteiros e preenchê-la com um zero e muitos 7FFFFFFFF's.
Linguagens gerenciadas
Você pode se perguntar por que isso funciona bem em idiomas gerenciados. Afinal, os idiomas gerenciados verificam os limites dos arrays com um branch para garantir que você não bagunce ...
Bem, não exatamente ... :-)
Tem havido bastante trabalho para eliminar esse branch para idiomas gerenciados. Por exemplo:
para (int i = 0; i  = 128)? c: 0;
}
// Teste
DateTime startTime = System.DateTime.Now;
soma longa = 0;
para (int i = 0; i <100000; ++ i)
{
// Loop primário
para (int j = 0; j  = 128. Isso significa que podemos facilmente extrair um único bit que nos dirá se queremos um valor ou não: deslocando os dados para os 7 bits à direita, ficamos com um bit 0 ou 1 bit, e só queremos adicionar o valor quando temos 1 bit. Vamos chamar esse bit de "bit de decisão".
Usando o valor 0/1 do bit de decisão como um índice em uma matriz, podemos criar um código que será igualmente rápido, quer os dados sejam classificados ou não. Nosso código sempre adicionará um valor, mas quando o bit de decisão for 0, adicionaremos o valor em algum lugar com o qual não nos importamos. Aqui está o código:
// Teste
clock_t start = clock ();
longo longo a [] = {0, 0};
soma longa longa;
para (sem sinal i = 0; i <100000; ++ i)
{
// Loop primário
for (sem sinal c = 0; c > 7);
a [j] + = dados [c];
}
}
double elapsedTime = static_cast  (clock () - iniciar) / CLOCKS_PER_SEC;
soma = a [1];
Este código desperdiça metade das adições, mas nunca falha na previsão de ramificação. É tremendamente mais rápido com dados aleatórios do que a versão com uma instrução if real.
Mas em meus testes, uma tabela de pesquisa explícita foi um pouco mais rápida do que isso, provavelmente porque a indexação em uma tabela de pesquisa foi um pouco mais rápida do que o deslocamento de bits. Isso mostra como meu código configura e usa a tabela de pesquisa (chamada sem imaginação de lut para "Tabela de pesquisa" no código). Aqui está o código C ++:
// Declare e preencha a tabela de pesquisa
int lut [256];
para (c sem sinal = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Use a tabela de pesquisa depois de construída
para (sem sinal i = 0; i <100000; ++ i)
{
// Loop primário
for (sem sinal c = 0; c  valor)
node = node-> pLeft;
outro
nó = nó-> pRight;
esta biblioteca faria algo como:
i = (x  valor);
nó = nó-> link [i];
Aqui está um link para este código: Red Black Trees, Eternally Confuzzled
|
No caso classificado, você pode fazer melhor do que confiar em uma previsão de branch bem-sucedida ou qualquer truque de comparação sem branch: remover completamente o branch.
Na verdade, a matriz é particionada em uma zona contígua com dados <128 e outra com dados> = 128. Portanto, você deve encontrar o ponto de partição com uma pesquisa dicotômica (usando Lg (arraySize) = 15 comparações) e, em seguida, fazer um acúmulo direto de esse ponto.
Algo como (desmarcado)
int i = 0, j, k = arraySize;
enquanto (i > 1;
if (dados [j]> = 128)
k = j;
outro
i = j;
}
soma = 0;
para (; i > 1;
para (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
para (soma = 0; i  = 128)
/ \
/ \
/ \
verdadeiro falso
/ \
/ \
/ \
/ \
B) soma + = dados [c]; C) para loop ou impressão ().
Sem a previsão de branch, ocorreria o seguinte:
Para executar a instrução B ou a instrução C, o processador terá que esperar até que a instrução A não alcance o estágio EX no pipeline, pois a decisão de ir para a instrução B ou a instrução C depende do resultado da instrução A. Portanto, o pipeline ficará assim.
quando se a condição retornar verdadeira:
Quando se a condição retornar falso:
Como resultado da espera pelo resultado da instrução A, o total de ciclos de CPU gastos no caso acima (sem previsão de desvio; para verdadeiro e falso) é 7.
Então, o que é previsão de branch?
O preditor de ramificação tentará adivinhar para que lado uma ramificação (uma estrutura if-then-else) irá antes que isso seja conhecido com certeza. Ele não irá esperar que a instrução A alcance o estágio EX do pipeline, mas adivinhará a decisão e irá para aquela instrução (B ou C no caso do nosso exemplo).
No caso de uma suposição correta, o pipeline se parece com isto:
Se for detectado posteriormente que a suposição estava errada, as instruções parcialmente executadas são descartadas e o pipeline é reiniciado com a ramificação correta, causando um atraso.
O tempo perdido no caso de uma predição incorreta do branch é igual ao número de estágios no pipeline, do estágio de busca ao estágio de execução. Os microprocessadores modernos tendem a ter pipelines bastante longos, de modo que o atraso na previsão incorreta fica entre 10 e 20 ciclos de clock. Quanto mais longo o pipeline, maior será a necessidade de um bom preditor de ramificação.
No código do OP, a primeira vez que for condicional, o preditor de desvio não possui nenhuma informação para basear a previsão, então na primeira vez ele escolherá aleatoriamente a próxima instrução. Posteriormente, no loop for, ele pode basear a previsão no histórico.
Para uma matriz classificada em ordem crescente, existem três possibilidades:
Todos os elementos são menores que 128
Todos os elementos são maiores que 128
Alguns novos elementos iniciais são menores que 128 e, posteriormente, tornam-se maiores que 128
Vamos supor que o preditor sempre assumirá o ramo verdadeiro na primeira execução.
Portanto, no primeiro caso, sempre levará o verdadeiroramo uma vez que historicamente todas as suas previsões estão corretas.
No segundo caso, inicialmente ele fará uma previsão errada, mas depois de algumas iterações, fará uma previsão correta.
No terceiro caso, ele irá inicialmente prever corretamente até que os elementos sejam menores que 128. Depois disso, ele irá falhar por algum tempo e se corrigirá quando vir falha de previsão de ramificação no histórico.
Em todos esses casos, a falha será em número muito menor e, como resultado, apenas algumas vezes será necessário descartar as instruções parcialmente executadas e reiniciar com o desvio correto, resultando em menos ciclos de CPU.
Mas, no caso de uma matriz aleatória não classificada, a previsão precisará descartar as instruções parcialmente executadas e reiniciar com o desvio correto na maioria das vezes e resultar em mais ciclos de CPU em comparação com a matriz classificada.
|
Uma resposta oficial seria de
Intel - Evitando o custo de erros de previsão de filiais
Intel - Reorganização de Branch and Loop para evitar erros de previsão
Artigos científicos - arquitetura de computador de previsão de ramos
Livros: J.L. Hennessy, D.A. Patterson: Arquitetura do computador: uma abordagem quantitativa
Artigos em publicações científicas: T.Y. Sim, Y.N. Patt fez muito disso nas previsões do branch.
Você também pode ver neste adorável diagrama porque o preditor de ramificação fica confuso.
Cada elemento no código original é um valor aleatório
dados [c] = std :: rand ()% 256;
então o preditor mudará de lado conforme o golpe std :: rand ().
Por outro lado, uma vez classificado, o preditor irá primeiro se mover para um estado de fortemente não tomado e quando os valores mudam para o valor alto, o preditor irá em três execuções através da mudança de fortemente não tomado para fortemente tomado.
|
Na mesma linha (acho que isso não foi destacado por nenhuma resposta) é bom mencionar que às vezes (especialmente em software onde o desempenho é importante - como no kernel do Linux) você pode encontrar algumas declarações if como as seguintes:
if (provável (everything_is_ok))
{
/* Faça alguma coisa */
}
ou similarmente:
if (improvável (very_improbable_condition))
{
/* Faça alguma coisa */
}
Provavelmente () e improvável () são na verdade macros definidas usando algo como __builtin_expect do GCC para ajudar o compilador a inserir o código de predição para favorecer a condição levando em consideração as informações fornecidas pelo usuário. O GCC suporta outros builtins que podem mudar o comportamento do programa em execução ou emitir instruções de baixo nível, como limpar o cache, etc. Veja esta documentação que analisa os builtins do GCC disponíveis.
Normalmente, esse tipo de otimização é encontrado principalmente em aplicativos de tempo real ou sistemas embarcados, onde o tempo de execução é importante e crítico. Por exemplo, se você está verificando alguma condição de erro que só acontece 1/10000000 vezes, por que não informar o compilador sobre isso? Dessa forma, por padrão, a previsão de ramificação assumiria que a condição é falsa.
|
As operações booleanas freqüentemente usadas em C ++ produzem muitas ramificações no programa compilado. Se esses branches estiverem dentro de loops e forem difíceis de prever, eles podem retardar a execução significativamente. Variáveis ​​booleanas são armazenadas como inteiros de 8 bits com o valor 0 para falso e 1 para verdadeiro.
Variáveis ​​booleanas são sobredeterminadas no sentido de que todos os operadores que têm variáveis ​​booleanas como entrada verificam se as entradas têm qualquer outro valor diferente de 0 ou 1, mas os operadores que têm booleanos como saída não podem produzir outro valor além de 0 ou 1. Isso faz com que as operações com Variáveis ​​booleanas como entrada menos eficientes do que o necessário.
Considere o exemplo:
bool a, b, c, d;
c = a && b;
d = a || b;
Isso normalmente é implementado pelo compilador da seguinte maneira:
bool a, b, c, d;
if (a! = 0) {
if (b! = 0) {
c = 1;
}
outro {
goto CFALSE;
}
}
outro {
CFALSE:
c = 0;
}
if (a == 0) {
if (b == 0) {
d = 0;
}
outro {
goto DTRUE;
}
}
outro {
DTRUE:
d = 1;
}
Este código está longe de ser ideal. Os ramos podem demorar muito em caso de erros de previsão. As operações booleanas podem ser muito mais eficientes se for conhecido com certeza que os operandos não têm outros valores além de 0 e 1. A razão pela qual o compilador não faz tal suposição é que as variáveis ​​podem ter outros valores se não forem inicializadas ou vêm de fontes desconhecidas. O código acima pode ser otimizado se aeb tiver sido inicializado com valores válidos ou se eles vierem de operadores que produzem saída booleana. O código otimizado tem a seguinte aparência:
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char é usado em vez de bool para tornar possível usar os operadores bit a bit (& e |) em vez dos operadores booleanos (&& e ||). Os operadores bit a bit são instruções únicas que levam apenas um ciclo de clock. O operador OR (|) funciona mesmo se aeb tiverem valores diferentes de 0 ou 1. O operador AND (&) e o operador EXCLUSIVE OR (^) podem fornecer resultados inconsistentes se os operandos tiverem valores diferentes de 0 e 1.
~ não pode ser usado para NOT. Em vez de,você pode fazer um NOT booleano em uma variável que é conhecida como 0 ou 1 fazendo um XOR com 1:
bool a, b;
b =! a;
pode ser otimizado para:
char a = 0, b;
b = a ^ 1;
a && b não pode ser substituído por a & b se b for uma expressão que não deve ser avaliada se a for falso (&& não avaliará b, & irá). Da mesma forma, um || b não pode ser substituído por a | b se b é uma expressão que não deve ser avaliada se a for verdadeiro.
Usar operadores bit a bit é mais vantajoso se os operandos forem variáveis ​​do que se os operandos forem comparações:
bool a; duplo x, y, z;
a = x> y && z <5,0;
é ideal na maioria dos casos (a menos que você espere que a expressão && gere muitas previsões erradas de ramos).
|
Isso é certeza!...
A previsão de ramificação torna a lógica mais lenta, por causa da troca que ocorre em seu código! É como se você estivesse indo em uma rua reta ou com muitas curvas, com certeza a reta vai ser feita mais rápido! ...
Se a matriz for classificada, sua condição é falsa na primeira etapa: dados [c]> = 128, então se torna um valor verdadeiro para todo o caminho até o final da rua. É assim que você chega ao fim da lógica mais rápido. Por outro lado, usando um array não classificado, você precisa de muito giro e processamento, o que torna seu código mais lento com certeza ...
Veja a imagem que criei para você abaixo. Qual rua será concluída mais rápido?
Portanto, de forma programática, a previsão de branch faz com que o processo seja mais lento ...
Também no final, é bom saber que temos dois tipos de previsões de branch, cada uma afetando seu código de maneira diferente:
1. Estático
2. Dinâmico
A previsão de ramificação estática é usada pelo microprocessador pela primeira vez
uma ramificação condicional é encontrada e a previsão de ramificação dinâmica é
usado para sucessivas execuções do código de desvio condicional.
A fim de escrever seu código de forma eficaz para aproveitar essas
regras, ao escrever instruções if-else ou switch, verifique o máximo
os casos comuns primeiro e vão progressivamente até os menos comuns.
Os loops não requerem necessariamente qualquer ordem especial de código para
previsão de ramificação estática, como apenas a condição do iterador de loop
normalmente é usado.
|
Esta pergunta já foi respondida de forma excelente muitas vezes. Ainda assim, gostaria de chamar a atenção do grupo para outra análise interessante.
Recentemente, este exemplo (modificado muito ligeiramente) também foi usado como uma forma de demonstrar como um trecho de código pode ser perfilado dentro do próprio programa no Windows. Ao longo do caminho, o autor também mostra como usar os resultados para determinar onde o código está gastando a maior parte do tempo, tanto no caso classificado como no não classificado. Finalmente, a peça também mostra como usar um recurso pouco conhecido do HAL (Hardware Abstraction Layer) para determinar o quanto de erro de predição de branch está acontecendo no caso não classificado.
O link está aqui:
Uma demonstração de autoperfil
|
Como já foi mencionado por outros, o que está por trás do mistério é o Preditor de Filial.
Não estou tentando acrescentar nada, mas explicando o conceito de outra maneira.
Há uma introdução concisa no wiki que contém texto e diagrama.
Eu gosto da explicação abaixo, que usa um diagrama para elaborar o Preditor de Ramificação intuitivamente.
Na arquitetura do computador, um preditor de ramo é um
circuito digital que tenta adivinhar para que lado um ramal (por exemplo, um
estrutura if-then-else) irá antes que isso seja conhecido com certeza. o
objetivo do preditor de ramo é melhorar o fluxo no
pipeline de instruções. Os preditores de ramos desempenham um papel crítico na
alcançando alto desempenho eficaz em muitos pipelines modernos
arquiteturas de microprocessador, como x86.
A ramificação bidirecional geralmente é implementada com um salto condicional
instrução. Um salto condicional pode ser "não executado" e continuar
execução com o primeiro ramo de código que segue imediatamente
após o salto condicional, ou pode ser "pego" e pular para um
lugar diferente na memória do programa, onde o segundo ramo do código é
armazenado. Não se sabe ao certo se um salto condicional será
tomadas ou não tomadas até que a condição tenha sido calculada e o
salto condicional passou do estágio de execução na instrução
pipeline (ver fig. 1).
Com base no cenário descrito, escrevi uma demonstração de animação para mostrar como as instruções são executadas em um pipeline em diferentes situações.
Sem o Predictor de Branch.
Sem a previsão de ramificação, o processador teria que esperar até o
a instrução de salto condicional passou pelo estágio de execução antes do
a próxima instrução pode entrar no estágio de busca no pipeline.
O exemplo contém três instruções e a primeira é uma instrução de salto condicional. As duas últimas instruções podem ir para o pipeline até que a instrução de salto condicional seja executada.
Levará 9 ciclos de clock para que as 3 instruções sejam concluídas.
Use Branch Predictor e não dê um salto condicional. Vamos supor que a previsão não está levando asalto condicional.
Levará 7 ciclos de clock para que as 3 instruções sejam concluídas.
Use Branch Predictor e dê um salto condicional. Vamos supor que a previsão não esteja dando o salto condicional.
Levará 9 ciclos de clock para que as 3 instruções sejam concluídas.
O tempo que é perdido em caso de erro de previsão de um ramal é igual a
o número de estágios no pipeline do estágio de busca ao
fase de execução. Os microprocessadores modernos tendem a ter
pipelines para que o atraso de erro de previsão esteja entre 10 e 20 clock
ciclos. Como resultado, tornar um pipeline mais longo aumenta a necessidade de um
preditor de ramo mais avançado.
Como você pode ver, parece que não temos um motivo para não usar o Preditor de Ramificação.
É uma demonstração bastante simples que esclarece a parte mais básica do Branch Predictor. Se esses gifs forem irritantes, sinta-se à vontade para removê-los da resposta e os visitantes também podem obter o código-fonte de demonstração ao vivo em BranchPredictorDemo
|
Ganho de previsão de ramo!
É importante entender que a predição incorreta do branch não desacelera os programas. O custo de uma previsão perdida é como se a previsão de ramificação não existisse e você esperasse pela avaliação da expressão para decidir qual código executar (mais explicações no próximo parágrafo).
if (expressão)
{
// Run 1
} outro {
// Run 2
}
Sempre que houver uma instrução if-else \ switch, a expressão deve ser avaliada para determinar qual bloco deve ser executado. No código de montagem gerado pelo compilador, são inseridas instruções de desvio condicional.
Uma instrução de desvio pode fazer com que um computador comece a executar uma sequência de instrução diferente e, assim, desvie de seu comportamento padrão de execução de instruções em ordem (ou seja, se a expressão for falsa, o programa pula o código do bloco if) dependendo de alguma condição, que é a expressão avaliação em nosso caso.
Dito isso, o compilador tenta prever o resultado antes de ser realmente avaliado. Ele irá buscar instruções do bloco if, e se a expressão for verdadeira, ótimo! Ganhamos o tempo necessário para avaliá-lo e progredimos no código; caso contrário, estamos executando o código errado, o pipeline é liberado e o bloco correto é executado.
Visualização:
Digamos que você precise escolher a rota 1 ou a rota 2. Esperando que seu parceiro verifique o mapa, você parou em ## e esperou ou poderia apenas escolher a rota 1 e, se tiver sorte (a rota 1 é a rota correta), então ótimo você não ter que esperar que seu parceiro checasse o mapa (você economizou o tempo que ele levaria para checar o mapa), senão você vai simplesmente voltar.
Embora a descarga de pipelines seja super rápida, hoje em dia vale a pena apostar. Prever dados classificados ou dados que mudam lentamente é sempre mais fácil e melhor do que prever mudanças rápidas.
O Route 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Rota 2 \ --------------------------------
|
No ARM, não há necessidade de ramificação, porque cada instrução tem um campo de condição de 4 bits, que testa (a custo zero) qualquer uma das 16 condições diferentes que podem surgir no Registrador de Status do Processador, e se a condição em uma instrução é false, a instrução é ignorada. Isso elimina a necessidade de ramificações curtas e não haveria nenhum acerto de previsão de ramificação para esse algoritmo. Portanto, a versão classificada desse algoritmo seria executada mais lentamente do que a versão não classificada no ARM, devido à sobrecarga extra de classificação.
O loop interno para este algoritmo seria semelhante ao seguinte na linguagem de montagem ARM:
MOV R0, # 0 // R0 = soma = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, dados // R2 = addr da matriz de dados (coloque esta instrução fora do loop externo)
.inner_loop // Rótulo da ramificação do loop interno
LDRB R3, [R2, R1] // R3 = dados [c]
CMP R3, # 128 // compare R3 a 128
ADICIONE R0, R0, R3 // se R3> = 128, então some + = dados [c] - nenhuma ramificação necessária!
ADICIONE R1, R1, # 1 // c ++
CMP R1, #arraySize // compare c a arraySize
BLT inner_loop // Ramifica para inner_loop se c  ());
for (sem sinal c = 0; c  = 128
soma = soma + dados1 (j);
fim
fim
fim
toc;
ExeTimeWithSorting = toc - tic;
Os resultados para o código MATLAB acima são os seguintes:
a: Tempo decorrido (sem classificação) = 3479,880861 segundos.
b: Tempo decorrido (com classificação) = 2377,873098 segundos.
Os resultados do código C como em @GManNickG recebo:
a: Tempo decorrido (sem classificação) = 19,8761 seg.
b: Tempo decorrido (com classificação) = 7,37778 seg.
Com base nisso, parece que o MATLAB é quase 175 vezes mais lento do que a implementação C sem classificação e 350 vezes mais lento com classificação. Em outras palavras, o efeito (de previsão de ramificação) é 1,46x para a implementação do MATLAB e 2,7x para a implementação C.
|
A suposição de outras respostas de que é necessário classificar os dados não é correta.
O código a seguir não classifica todo o array, mas apenas segmentos de 200 elementos dele e, portanto, é executado mais rapidamente.
Classificar apenas as seções do elemento k completa o pré-processamento em tempo linear, O (n), em vez do tempo O (n.log (n)) necessário para classificar toda a matriz.
#include 
#include 
#include 
int main () {
dados internos [32768]; const int l = sizeof data / sizeof data [0];
para (sem sinal c = 0; c  = 128)
soma + = dados [c];
}
}
std :: cout << static_cast  (clock () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << sum << std :: endl;
}
Isso também "prova" que não tem nada a ver com qualquer problema de algoritmo, como ordem de classificação, e é, de fato, previsão de ramificação.
|
Resposta de Bjarne Stroustrup a esta pergunta:
Isso soa como uma pergunta de entrevista. É verdade? Como você saberia? É uma má ideia responder a perguntas sobre eficiência sem primeiro fazer algumas medições, por isso é importante saber como medir.
Então, eu tentei com um vetor de um milhão de inteiros e obtive:
Já classificou 32995 milissegundos
Ordem aleatória de 125944 milissegundos
Já classificou 18610 milissegundos
Embaralhado 133.304 milissegundos
Já ordenou 17942 milissegundos
Embaralhado 107858 milissegundos
Corri algumas vezes para ter certeza. Sim, o fenômeno é real. Meu código-chave era:
void run (vetor  & v, string const & label)
{
t0 automático = system_clock :: now ();
sort (v.begin (), v.end ());
auto t1 = system_clock :: now ();
etiqueta cout <<
<< duration_cast  (t1 - t0) .count ()
<< "milissegundos \ n";
}
void tst ()
{
vetor  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "já classificado");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
executar (v, "embaralhado");
}
Pelo menos o fenômeno é real com este compilador, biblioteca padrão e configurações do otimizador. Implementações diferentes podem e fornecem respostas diferentes. Na verdade, alguém fez um estudo mais sistemático (uma pesquisa rápida na web o encontrará) e a maioria das implementações mostra esse efeito.
Uma razão é a previsão de ramificação: a operação-chave no algoritmo de classificação é “if (v [i]  = 128. Isso significa que podemos facilmente extrair um único bit que nos dirá se queremos um valor ou não: deslocando os dados para os 7 bits certos, ficamos com um bit 0 ou 1 bit, e só queremos adicionar o valor quando temos um bit 1. Vamos chamar esse bit de "bit de decisão".
Usando o valor 0/1 do bit de decisão como um índice em uma matriz, podemos criar um código que será igualmente rápido, quer os dados sejam classificados ou não. Nosso código sempre adicionará um valor, mas quando o bit de decisão for 0, adicionaremos o valor em algum lugar com o qual não nos importamos. Aqui está o código:
// Teste
clock_t start = clock ();
longo longo a [] = {0, 0};
soma longa longa;
para (sem sinal i = 0; i <100000; ++ i)
{
// Loop primário
for (sem sinal c = 0; c > 7);
a [j] + = dados [c];
}
}
double elapsedTime = static_cast  (clock () - iniciar) / CLOCKS_PER_SEC;
soma = a [1];
Este código desperdiça metade das adições, mas nunca falha na previsão de ramificação. É tremendamente mais rápido com dados aleatórios do que a versão com uma instrução if real.
Mas em meus testes, uma tabela de pesquisa explícita foi um pouco mais rápida do que isso, provavelmente porque a indexação em uma tabela de pesquisa foi um pouco mais rápida do que o deslocamento de bits. Isso mostra como meu código configura e usa a tabela de pesquisa (chamada sem imaginação de lut para "Tabela de pesquisa" no código). Aqui está o código C ++:
// Declare e preencha a tabela de pesquisa
int lut [256];
para (c sem sinal = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Use a tabela de pesquisa depois de construída
para (sem sinal i = 0; i <100000; ++ i)
{
// Loop primário
for (sem sinal c = 0; c  valor)
node = node-> pLeft;
outro
nó = nó-> pRight;
esta biblioteca faria algo como:
i = (x  valor);
nó = nó-> link [i];
É uma boa solução e talvez funcione.
|
Questão altamente ativa. Ganhe 10 reputação para responder a esta pergunta. O requisito de reputação ajuda a proteger essa pergunta contra spam e atividades sem resposta.
Não é a resposta que você está procurando? Navegue por outras questões com a tag java c ++ performance optimization branch-prediction ou faça sua própria pergunta.